﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using WindowsFormsApp1;

namespace doveData
{
    public class StationGraph<T>//图
    {
        private List<Vertex<T>> _items;//图的顶点集合
        public float[,] Edges;

        private int _capacity;

        private int INF = 65535;

        public StationGraph() : this(10) { }//构造方法


        public StationGraph(int cap)//指定容量的构造方法
        {
            _capacity = cap;
            _items = new List<Vertex<T>>(cap);
            Edges = new float[_capacity, _capacity];
            InitMatrix();
        }


        public int Count
        {
            get { return _items.Count; }
        }

        public int Capacity
        {
            get { return _capacity; }
        }


        public T GetItem(int index)//索引器
        {
            if (index >= 0 && index <= _items.Count - 1)
            {
                return _items[index].Data;
            }
            else
            {
                throw new Exception("索引超出范围！");
            }
        }



        public void AddVertex(T item)
        {
            if (Count == _capacity) //已经满了
            {
                _capacity *= 2;
                List<Vertex<T>> newList = new List<Vertex<T>>(_capacity);
                newList.AddRange(_items);
                _items = newList;
                Edges = new float[_capacity, _capacity];
            }
            //不允许插入重复值
            if (Contains(item))
            {
                //throw new ArgumentException("插入了重复顶点！");
                Console.WriteLine("插入了重复顶点:{0}！", item);
                return;
            }
            _items.Add(new Vertex<T>(item));

        }

        public void AddEdgeM(T from, T to, float dist)
        {
            Vertex<T> fromVer = Find(from);
            if (fromVer == null)
            {
                //throw new ArgumentException("头顶点不存在!");
                Console.WriteLine("头顶点不存在!");
                return;
            }
            Vertex<T> toVer = Find(to);
            if (toVer == null)
            {
                // throw new ArgumentException("尾顶点不存在！");
                Console.WriteLine("尾顶点不存在！");
                return;
            }
            //无向边的两个顶点都需记录边信息
            AddDirectedEdgeM(fromVer, toVer, dist);
            AddDirectedEdgeM(toVer, fromVer, dist);
        }

        public bool Contains(T item)//查找图中是否包含某项
        {
            foreach (Vertex<T> v in _items)
            {
                if (v.Data.Equals(item))
                {
                    return true;
                }
            }
            return false;
        }



        private Vertex<T> Find(T item)
        {
            foreach (Vertex<T> v in _items)
            {
                if (v.Data.Equals(item))
                {
                    return v;
                }
            }
            return null;
        }

        private void AddDirectedEdgeM(Vertex<T> fromVer, Vertex<T> toVer, float dist)
        {
            Edges[_items.IndexOf(fromVer), _items.IndexOf(toVer)] = dist;
        }

        public bool ContainEdge(T from, T to)
        {
            Vertex<T> fromVer = Find(from);
            if (fromVer == null)
            {
                //throw new ArgumentException("头顶点不存在!");
                Console.WriteLine("头顶点不存在!");
                return false;
            }
            Vertex<T> toVer = Find(to);
            if (toVer == null)
            {
                // throw new ArgumentException("尾顶点不存在！");
                Console.WriteLine("尾顶点不存在！");
                return false;
            }
            Node tmp,//用于表示链表末尾结点
            node = fromVer.FirstEdge;//下一结点
            do
            {
                //检查是否添加了重复边
                if (node.Adjvex.Data.Equals(toVer.Data))
                {
                    // throw new ArgumentException("添加了重复的边！");
                    Console.WriteLine("添加了重复的边:{0}->{1}！", fromVer.Data, toVer.Data);
                    return true;
                }
                tmp = node;
                node = node.Next;
            } while (node != null);
            return false;
        }

        public void InitMatrix()
        {

            for (int i = 0; i < _capacity; i++)
            {
                for (int j = 0; j < _capacity; j++)
                {
                    Edges[i, j] = INF;
                }
            }
        }

        public override string ToString() //仅用于测试
        {   //打印每个节点和它的邻接点
            string s = string.Empty;
            foreach (Vertex<T> v in _items)
            {
                s += v.Data.ToString() + ":";
                for (int i = 0; i < _capacity; i++)
                {
                    if (Edges[_items.IndexOf(v), i] != INF)
                    {
                        s += _items[i].Data.ToString();
                    }
                }
                s += "\n\n\r";
            }
            return s;
        }


        #region BFS广度优先遍历
        //邻接矩阵
        public void BFSMTraverse()
        {
            InitVisited();
            BFSM(_items[0]);
        }
        private void BFSM(Vertex<T> k)
        {
            Queue<Vertex<T>> q = new Queue<Vertex<T>>();
            Console.WriteLine(k.Data.ToString());
            k.Visited = true;
            q.Enqueue(k);
            while (q.Count != 0)
            {
                k = q.Dequeue();
                for (int i = 0; i < _items.Count; i++)
                {
                    if (Edges[i, _items.IndexOf(k)] != INF && _items[i].Visited == false)
                    {
                        Console.WriteLine(_items[i].Data.ToString());
                        _items[i].Visited = true;
                        q.Enqueue(_items[i]);
                    }
                }
            }
        }

        public void CheckMatrix()
        {
            for (int i = 0; i < _capacity; i++)
            {
                for (int j = 0; j < _capacity; j++)
                {
                    Console.Write(Edges[i, j] + " ");
                }
                Console.WriteLine("");
            }
        }
        private void InitVisited()
        {
            foreach (Vertex<T> item in _items)
            {
                item.Visited = false;
            }
        }
        #endregion

        #region Dijkstra算法求最短路径

        public void ShortestPath_DIJ(int from)
        {
            float min;
            Vertex<T> pre;
            Vertex<T> m = _items[from];
            Vertex<T>[] P = new Vertex<T>[Count];//源点到某点最短路径上的前驱顶点
            float[] D = new float[Count];//源点到某点v的最短路径的长
            bool[] final = new bool[Count];//final[v]为true时有最短路径
            //初始化
            for (int j = 0; j < Count; j++)
            {
                D[j] = Edges[from, j];
                final[j] = false;
                if (D[j] < INF) P[j] = _items[from];
                else P[j] = null;
            }
            D[from] = 0;
            final[from] = true;
            //主循环
            for (int j = 0; j < Count; j++)
            {
                min = INF;
                for (int k = 0; k < Count; k++)
                {
                    if (!final[k] && D[k] < min)
                    {
                        min = D[k];
                        m = _items[k];
                    }
                }
                final[_items.IndexOf(m)] = true;
                for (int k = 0; k < Count; k++)
                {
                    if ((!final[k]) && ((min + Edges[_items.IndexOf(m), k]) < D[k]))
                    {
                        D[k] = min + Edges[_items.IndexOf(m), k];
                        P[k] = m;
                    }
                }
            }
            Console.Write("\n");
            for (int j = 0; j < Count; j++)
            {
                Console.Write(D[j] + "\t" + _items[j].Data.ToString());
                pre = P[j];
                while (pre != null)
                {
                    Console.Write("<--" + pre.Data.ToString());
                    pre = P[_items.IndexOf(pre)];
                }
                Console.WriteLine("");
            }
        }

        public void ShortestPath_DIJ(int from, int to)
        {
            float min;
            Vertex<T> pre;
            Vertex<T> m = _items[from];
            Vertex<T>[] P = new Vertex<T>[Count];//源点到某点最短路径上的前驱顶点
            float[] D = new float[Count];//源点到某点v的最短路径的长
            bool[] final = new bool[Count];//final[v]为true时有最短路径
            //初始化
            for (int j = 0; j < Count; j++)
            {
                D[j] = Edges[from, j];
                final[j] = false;
                if (D[j] < INF) P[j] = _items[from];
                else P[j] = null;
            }
            D[from] = 0;
            final[from] = true;
            //主循环
            for (int j = 0; j < Count; j++)
            {
                min = INF;
                for (int k = 0; k < Count; k++)
                {
                    if (!final[k] && D[k] < min)
                    {
                        min = D[k];
                        m = _items[k];
                    }
                }
                final[_items.IndexOf(m)] = true;
                for (int k = 0; k < Count; k++)
                {
                    if ((!final[k]) && ((min + Edges[_items.IndexOf(m), k]) < D[k]))
                    {
                        D[k] = min + Edges[_items.IndexOf(m), k];
                        P[k] = m;
                    }
                }
            }
            Console.Write("\n");

            Console.Write(D[to] + "\t" + _items[to].Data.ToString());
            pre = P[to];
            while (pre != null)
            {
                Console.Write("<--" + pre.Data.ToString());
                pre = P[_items.IndexOf(pre)];
            }
            Console.WriteLine("");

        }

        public float GetShortestPath_DIJ(int from, int to)
        {
            Stack<string> path=new Stack<string>();
            float min;
            Vertex<T> pre;
            Vertex<T> m = _items[from];
            Vertex<T>[] P = new Vertex<T>[Count];//源点到某点最短路径上的前驱顶点
            float[] D = new float[Count];//源点到某点v的最短路径的长
            bool[] final = new bool[Count];//final[v]为true时有最短路径
            //初始化
            for (int j = 0; j < Count; j++)
            {
                D[j] = Edges[from, j];
                final[j] = false;
                if (D[j] < INF) P[j] = _items[from];
                else P[j] = null;
            }
            D[from] = 0;
            final[from] = true;
            //主循环
            for (int j = 0; j < Count; j++)
            {
                min = INF;
                for (int k = 0; k < Count; k++)
                {
                    if (!final[k] && D[k] < min)
                    {
                        min = D[k];
                        m = _items[k];
                    }
                }
                final[_items.IndexOf(m)] = true;
                for (int k = 0; k < Count; k++)
                {
                    if ((!final[k]) && ((min + Edges[_items.IndexOf(m), k]) < D[k]))
                    {
                        D[k] = min + Edges[_items.IndexOf(m), k];
                        P[k] = m;
                    }
                }
            }
            Console.Write("\n");
            pre = P[to];
            path.Push(_items[to].Data.ToString());
            while (pre != null)
            {
                //Console.Write("<--" + pre.Data.ToString());
                path.Push(pre.Data.ToString());
                pre = P[_items.IndexOf(pre)];
            }
            int pathCount = path.Count;
            for (int i = 0; i < pathCount; i++)
            {
                if (i != 0)
                {
                    Console.Write("-->");
                }
                else
                {
                    Console.Write("\t\t\t\t\t");
                }
                Console.Write(path.Pop());
            }
            Console.WriteLine("");
            return D[to];
        }

        public LinePath W_GetShortestPath_DIJ(int from, int to)
        {
            Stack<T> path = new Stack<T>();
            float min;
            Vertex<T> pre;
            Vertex<T> m = _items[from];
            Vertex<T>[] P = new Vertex<T>[Count];//源点到某点最短路径上的前驱顶点
            float[] D = new float[Count];//源点到某点v的最短路径的长
            bool[] final = new bool[Count];//final[v]为true时有最短路径
            //初始化
            for (int j = 0; j < Count; j++)
            {
                D[j] = Edges[from, j];
                final[j] = false;
                if (D[j] < INF) P[j] = _items[from];
                else P[j] = null;
            }
            D[from] = 0;
            final[from] = true;
            //主循环
            for (int j = 0; j < Count; j++)
            {
                min = INF;
                for (int k = 0; k < Count; k++)
                {
                    if (!final[k] && D[k] < min)
                    {
                        min = D[k];
                        m = _items[k];
                    }
                }
                final[_items.IndexOf(m)] = true;
                for (int k = 0; k < Count; k++)
                {
                    if ((!final[k]) && ((min + Edges[_items.IndexOf(m), k]) < D[k]))
                    {
                        D[k] = min + Edges[_items.IndexOf(m), k];
                        P[k] = m;
                    }
                }
            }
            Console.Write("\n");
            pre = P[to];
            path.Push(_items[to].Data);
            while (pre != null)
            {
                //Console.Write("<--" + pre.Data.ToString());
                path.Push(pre.Data);
                pre = P[_items.IndexOf(pre)];
            }
            int pathCount = path.Count;
            LinePath outputPath=new LinePath();
            for (int i = 0; i < pathCount; i++)
            {
                if (i != 0)
                {
                    Console.Write("-->");
                }
                else
                {
                    Console.Write("\t\t\t\t\t");
                }
                outputPath.Items.Add(path.Pop());
            }
            outputPath.LengthOfPath = D[to];
            
            return outputPath;
        }
        #endregion


        #region 嵌套类 结点Node 表头Vertex
        //链表中的表结点
        public class Node
        {
            public Vertex<T> Adjvex;//邻接点域
            public Node Next;//下一个邻接点域
            public float Distance;

            public Node(Vertex<T> value)
            {
                Distance = 1;
                Adjvex = value;
            }
            public Node(Vertex<T> value, float dist)
            {
                Distance = dist;
                Adjvex = value;
            }
        }



        //表示存放于数组中的表头结点
        public class Vertex<TValue>
        {
            public TValue Data;//数据
            public Node FirstEdge;//邻接链表头指针
            public Boolean Visited;//访问标记

            public Vertex(TValue value)//构造方法
            {
                Data = value;
            }
        }
        #endregion

    }

}
